/**
 * @ClassName Offer53II
 * @Description 剑指 Offer 53 - II. 0～n-1中缺失的数字
 * @Author clockTown
 * @Date 2021/8/15 20:18
 * @Version 1.0
 */
class Offer53II {
}

/**
 * v0 遍历
 */
class Offer53IIV0 {
    public int missingNumber(int[] nums) {
        int i = 0;
        for (int num : nums) {
            if (num != i){
                return i;
            }
            i++;
        }
        return i;
    }
}

/**
 * v1 二分查找
 */
class Offer53IIV1 {
    public int missingNumber(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right){
            int mid = (left + right) >> 1;
            if (nums[mid] == mid){
                left = mid + 1;
            }else {
                right = mid - 1;
            }
        }

        return left;
    }
}